알고리즘 풀이 - 삼각 달팽이
January 09, 2021
삼각 달팽이
문제 요약
제한사항
- n은 1 이상 1,000 이하입니다.
Input
- 정수 n(삼각형의 높이)
output
- 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열
해결방법
- up, down, fill의 세가지 상태로 나누어 상태에 따라 처리
- 삼각형을 우선 만들고 배열을 합쳐서 리턴
function solution(n) {
const triangle = []
const meta = []
let totalCount = 0
for (let i = 0; i < n; i++) {
triangle.push(new Array(i + 1))
meta.push({ start: 0, end: i })
totalCount += i + 1
}
let mode = 'DOWN'
let line = 0
for (let i = 1; i <= totalCount; i++) {
if (mode === 'DOWN') {
triangle[line][meta[line].start] = i
meta[line].start++
line++
const nextLine = meta[line + 1]
if (nextLine === undefined || nextLine.end < nextLine.start) {
mode = 'FILL'
}
} else if (mode === 'FILL') {
triangle[line][meta[line].start] = i
meta[line].start++
if (meta[line].start > meta[line].end) {
mode = 'UP'
line--
}
} else if (mode === 'UP') {
triangle[line][meta[line].end] = i
meta[line].end--
line--
const nextLine = meta[line]
if (nextLine === undefined || nextLine.end < nextLine.start) {
mode = 'DOWN'
line += 2
}
}
}
const result = triangle.reduce((prev, curr) => prev.concat(curr))
return result
}개선사항
다른 사람의 모범 풀이
소스 내부 동작을 직관적으로 이해하기는 힘들지만 소스가 간결하고 예쁘다.
해당 소스를 보면서 내 소스의 변수명도 변경해야겠다는 생각이 든다.
array.flat() 함수의 존재를 알았다.
function solution(n) {
let a = Array(n)
.fill()
.map((_, i) => Array(i + 1).fill())
let row = -1
let col = 0
let fill = 0
for (let i = n; i > 0; i -= 3) {
a[++row][col] = ++fill
for (let j = 0; j < i - 1; j++) a[++row][col] = ++fill
for (let j = 0; j < i - 1; j++) a[row][++col] = ++fill
for (let j = 0; j < i - 2; j++) a[--row][--col] = ++fill
}
return a.flat()
}리팩토링
function solution(n) {
const result = []
const meta = []
let totalCount = 0
for (let i = 0; i < n; i++) {
result.push(new Array(i + 1))
meta.push({ start: 0, end: i })
totalCount += i + 1
}
let mode = 'DOWN'
let row = 0
for (let i = 1; i <= totalCount; i++) {
if (mode === 'DOWN') {
result[row][meta[row].start] = i
meta[row].start++
row++
const nextLine = meta[row + 1]
if (nextLine === undefined || nextLine.end < nextLine.start) {
mode = 'FILL'
}
} else if (mode === 'FILL') {
result[row][meta[row].start] = i
meta[row].start++
if (meta[row].start > meta[row].end) {
mode = 'UP'
row--
}
} else if (mode === 'UP') {
result[row][meta[row].end] = i
meta[row].end--
row--
const nextLine = meta[row]
if (nextLine === undefined || nextLine.end < nextLine.start) {
mode = 'DOWN'
row += 2
}
}
}
return result.flat()
}